KDD 2020 开源论文 | 稀疏优化的块分解算法
©PaperWeekly 原创 · 作者｜袁淦钊
单位｜鹏城实验室
研究方向｜数值优化、机器学习
这次向大家分享的工作是鹏城实验室牵头，联合腾讯 AI 实验室和中山大学在 SIGKDD 2020 上发表的文章：A Block Decomposition Algorithm for Sparse Optimization。
稀疏优化由于其内在的组合结构，一般比较难求解。组合搜索方法可以获得其全局最优解，但往往局限于小规模的优化问题；坐标下降方法速度快，但往往陷入于一个较差的局部次优解中。
我们提出一种结合组合搜索和坐标下降的块 K 分解算法。具体地说，我们考虑随机策略或/和贪婪策略，选择 K 个坐标作为工作集，然后基于原始目标函数对工作集坐标进行全局组合搜索。我们对块 K 分解算法进行了最优性分析，我们证明了我们的方法比现有的方法找到更强的稳定点。
此外，我们还对算法进行了收敛性分析，并构建其收敛速度。大量的实验表明，我们的方法目前取得的性能臻于艺境。我们的块 K 分解算法的工作发表在国际人工智能会议 SIGKDD 2020 和 CVPR 2019 上。
本文主要讨论求解以下稀疏约束或稀疏正则优化问题：
我们假设 f(x) 是光滑的凸函数。这类问题在压缩感知、信号处理、统计学习等问题上有着广泛的应用。
以下是我们提出的块 K 分解算法：
算法非常简洁，只有两步。第一步：选择 K 个坐标集，第二步：基于原始目标函数 f(x)，对选择的 K 个坐标作全局组合搜索。
该算法也被称为块坐标下降方法，但和以往方法有所不同，有以下四点值得注意：
我们使用了临近点策略，这个策略是为了保证充分下降条件和全局收敛性质；
我们直接求解原来具有组合结构的子问题，而不使用替代函数最小化其上界； 在坐标选择上，以往可以根据一阶最优条件 / KKT 条件残差来选择坐标，但这种策略对于非凸问题不再适用。我们采用两种策略。一种是随机策略，这种策略的最大的好处是保证算法得到块 K 稳定点（下方将讨论）；另一种是贪心策略，这种策略直接根据目标值下降的多少来选择坐标，在实际中通常可以加速算法收敛； 在求解子问题中，虽然子问题是 NP 难的，且没有快速的封闭解，但是我们依然可使用全局树形搜索获得全局最优点。注意，K 通常是一个很小的整数；例如，在我们的实验中，K=16。我们考虑简单的二次函数例子：。我们先系统地穷举下面的全二叉树，通过求解 个线性系统得到所有可能的局部极小值；然后我们选出使得目标值达到最小的那个作为最优解。
目前常见的稀疏优化方法有四类：
a. 第一类是松弛近似方法。这类方法最大的缺点是不能直接每一步控制问题的稀疏特性。
我们方法优点：可以直接控制解的稀疏特性。
b. 第二类是贪心算法。这类方法最大的缺点是初始化点必须为空集或零。
我们方法优点：可以任意初始化，而且最终精度对初始化不敏感。
c. 第三类方法是全局优化算法。这类方法的最大缺点是仅限于小规模问题。
我们方法优点：利用了全局最优化算法，提高了算法精度。
d. 第四类方法是临近梯度方法。这类方法的最大缺点是算法陷入到较差的局部次优值。
我们方法优点：从理论和实验上都优胜于临近梯度方法。
以下我们定义稀疏优化问题的稳定点：基本稳定点、李普希茨稳定点，块 K 稳定点。
基本稳定点就是指，当非零元指标集已知时，解达到全局最优。这类稳定点的一个很好的性质是：稳定点是可枚举的，这使得我们能够验证某个解是否是该问题的全局最优解。
李普希茨稳定点是通过一个临近算子来刻画，经典的临近梯度法得到的是李普希茨稳定点。临近梯度法每一步需要求解一个临近算子，该算子有快速封闭解，但是这种简单的上界替代函数方法通常导致算法精度不高。
这是我们提出的块 K 稳定点的概念。块 K 稳定点是指，当我们（全局地）最小化任意的 K 个坐标（其余的 n-K 个坐标固定不变），我们都不能使得目标函数值得到改进。
我们得到以下的关于这三类稳定点的层次关系：
我们已证明，我们的块 K 稳定点比以往的基本稳定点和李普希茨稳定点更强。可以以上图举例。假如我们从上方的图中的绿色区域（块 K 稳定点）选择一个点，该点落入黄色区域（最优点集）中有一个概率 P1；我们从上方的图中的红色区域（李普希茨稳定点）选择一个点，该点落入黄色区域（最优点集）中有一个概率 P2。由于 P1 总是大于 P2，因此我们的方法更大的概率落入最优解集中。
稀疏优化问题由于其组合结构，完全求解这个问题属于大海捞针。我们对稀疏优化问题的全局最优点有了更准确细致的描述，我们对这类问题给出了更精确的近似。
可以打个比喻：甲说，鹏城实验室在广东；乙说，鹏城实验室在广东深圳；丙说，鹏城实验室在广东深圳南山区万科云城（详细广告信息可参考本文下方）。丙的说法更准确。
收敛性分析
我们证明了算法在期望意义上收敛到块 K 稳定点。
此外，我们证明了算法线性收敛性质（我想大家可能不太感兴趣，可参考我的论文和 PPT）。
6.1 对于稀疏约束优化问题，我们比较了以下9种方法：
Proximal Gradient Method (PGM)
Accerlated Proximal Gradient Method (APGM)
Quadratic Penalty Method (QPM)
Subspace Pursuit (SSP)
Regularized Orthogonal Matching Pursuit (ROMP)
Orthogonal Matching Pursuit (OMP)
Compressive Sampling Matched Pursuit (CoSaMP)
Convex `1 Approximation Method (CVX-L1)
Proposed Decomposition Method (DEC-RiGj, 我们的方法)
实验1
结论1
我们的分解方法精度优于其它方法。此外，K 越大，精度越高；
使用贪心策略选择 2 个坐标和使用随机策略选择 2 个坐标两种策略相比，前者收敛快但精度差，因此两种坐标选择策略需要结合来使用；
我们的方法在 30 秒内收敛。
实验2
结论2
基于迭代硬阈值的方法 {PGM, APGM, QPM} 性能较差；
OMP 和 ROMP 有时性能较差；
在这几个数据集中，我们的方法一致地和较大地优于目前的方法。
6.2 对于稀疏正则优化问题，我们比较了以下5中算法：
PGM-L0: PGM for L0 Problem APGM-L0: Accerlated PGM for L0 Problem PGM-L1: PGM for L1 Problem PGM-Lp: PGM for Lp Problem (p=1/2) Proposed Decomposition Method (我们的方法)
实验1
结论1
PGM-Lp 比 PGM-L1 所取得的精度要好；
在所有数据集上，我们的分解算法总的来说比其他的方法要好。
总结全文
招聘
鹏城实验室诚聘 博士后 / 助理研究员（数值优化方向）
岗位名称：博士后/助理研究员
工作地点：鹏城实验室（深圳南山区万科云城）
研究方向：数值算法/（半）离散优化/二阶优化/非凸优化/非光滑优化/机器学习
应聘材料：个人简历+学术成果（论文、科研项目、所获奖项等）发送到下方邮箱
应聘条件：35岁以下近三年内取得计算机/计算数学等学科博士学位+在数值优化/机器学习/机器视觉/数据挖掘等领域以第一作者发表过高水平论文（e.g., CCF A类/SIAM Journal）
岗位待遇：全球范围内有竞争力。
联系方式：yuangzh@pcl.ac.cn
更多阅读
#投 稿 通 道#
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。
📝 来稿标准：
• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向）
• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志
📬 投稿邮箱：
• 投稿邮箱：hr@paperweekly.site
• 所有文章配图，请单独在附件中发送
• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。